package exp7;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;

/**
 * Function: Sorting
 * Editor: HexWarrior6
 * Date: 2023/12/4 15:50
 */
public class MySort {
    public static void main(String[] args) {
        final int N = (int) 1e4;
        Integer[] arr = new Integer[N];
        Random rand = new Random();
        HashSet<Integer> flag = new HashSet<>();
        for (int i = 0; i < N; i++) {
            int n = rand.nextInt(N);
            if (flag.contains(n)) {
                i--;
            } else {
                arr[i] = n;
                flag.add(n);
            }
        }
        long start, end;

        Integer[] arr1 = arr.clone();
        start = System.nanoTime();
        selectionSort(arr1);
        end = System.nanoTime();
        System.out.println("selectionSort: " + (end - start));

        Integer[] arr2 = arr.clone();
        start = System.nanoTime();
        bubbleSort(arr2);
        end = System.nanoTime();
        System.out.println("bubbleSort:    " + (end - start));

        Integer[] arr3 = arr.clone();
        start = System.nanoTime();
        insertionSort(arr3);
        end = System.nanoTime();
        System.out.println("insertionSort: " + (end - start));

        Integer[] arr4 = arr.clone();
        start = System.nanoTime();
        shellSort(arr4);
        end = System.nanoTime();
        System.out.println("shellSort:     " + (end - start));

        Integer[] arr5 = arr.clone();
        start = System.nanoTime();
        heapSort(arr5);
        end = System.nanoTime();
        System.out.println("heapSort:      " + (end - start));

        Integer[] arr6 = arr.clone();
        start = System.nanoTime();
        mergeSort(arr6);
        end = System.nanoTime();
        System.out.println("mergeSort:     " + (end - start));

        Integer[] arr7 = arr.clone();
        start = System.nanoTime();
        quicksort(arr7);
        end = System.nanoTime();
        System.out.println("quicksort:     " + (end - start));

        int[] arr8 = Arrays.stream(arr).mapToInt(Integer::valueOf).toArray();
        start = System.nanoTime();
        bucketSort(arr8);
        end = System.nanoTime();
        System.out.println("bucketSort:    " + (end - start));

        Integer[] arr9 = arr.clone();
        start = System.nanoTime();
        radixSort(arr9);
        end = System.nanoTime();
        System.out.println("radixSort:     " + (end - start));
    }

    public static <AnyType extends Comparable<? super AnyType>> void selectionSort(AnyType[] a) {
        for (int i = 0; i < a.length; i++) {
            int k = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[k].compareTo(a[j]) > 0) {
                    k = j;
                }
            }
            AnyType temp = a[k];
            a[k] = a[i];
            a[i] = temp;
        }
    }

    public static <AnyType extends Comparable<? super AnyType>> void bubbleSort(AnyType[] a) {
        for (int i = 0; i < a.length; i++) {
            for (int j = a.length - 1; j > i; j--) {
                if (a[j].compareTo(a[j - 1]) < 0) {
                    AnyType temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
    }

    public static <AnyType extends Comparable<? super AnyType>> void insertionSort(AnyType[] a) {
        int j;
        for (int p = 1; p < a.length; p++) {
            AnyType tmp = a[p];
            for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    public static <AnyType extends Comparable<? super AnyType>> void shellSort(AnyType[] a) {
        int j;
        for (int gap = a.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < a.length; i++) {
                AnyType tmp = a[i];
                for (j = i; j >= gap && tmp.compareTo(a[j - gap]) < 0; j -= gap) {
                    a[j] = a[j - gap];
                }
                a[j] = tmp;
            }
        }
    }

    private static int leftChild(int i) {
        return 2 * i + 1;
    }

    private static <AnyType extends Comparable<? super AnyType>>
    void percDown(AnyType[] a, int i, int n) {
        int child;
        AnyType tmp;
        for (tmp = a[i]; leftChild(i) < n; i = child) {
            child = leftChild(i);
            if (child != n - 1 && a[child].compareTo(a[child + 1]) < 0) {
                child++;
            }
            if (tmp.compareTo(a[child]) < 0) {
                a[i] = a[child];
            } else {
                break;
            }
        }
        a[i] = tmp;
    }

    public static <AnyType extends Comparable<? super AnyType>> void swapReferences(AnyType[] a, int i, int j) {
        AnyType temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static <AnyType extends Comparable<? super AnyType>> void heapSort(AnyType[] a) {
        for (int i = a.length / 2 - 1; i >= 0; i--) /* buildHeap */ {
            percDown(a, i, a.length);
        }
        for (int i = a.length - 1; i > 0; i--) {
            swapReferences(a, 0, i); /* deleteMax */
            percDown(a, 0, i);
        }
    }

    private static <AnyType extends Comparable<? super AnyType>> void merge(AnyType[] a, AnyType[] tmpArray,
                                                                            int leftPos, int rightPos, int rightEnd) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;

        // Main loop
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            if (a[leftPos].compareTo(a[rightPos]) <= 0) {
                tmpArray[tmpPos++] = a[leftPos++];
            } else {
                tmpArray[tmpPos++] = a[rightPos++];
            }
        }

        while (leftPos <= leftEnd) // Copy rest of first half
        {
            tmpArray[tmpPos++] = a[leftPos++];
        }

        while (rightPos <= rightEnd) // Copy rest of right half
        {
            tmpArray[tmpPos++] = a[rightPos++];
        }

        // Copy tmpArray back
        for (int i = 0; i < numElements; i++, rightEnd--) {
            a[rightEnd] = tmpArray[rightEnd];
        }
    }


    private static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a, AnyType[] tmpArray, int left, int right) {
        if (left < right) {
            int center = (left + right) / 2;
            mergeSort(a, tmpArray, left, center);
            mergeSort(a, tmpArray, center + 1, right);
            merge(a, tmpArray, left, center + 1, right);
        }
    }

    public static <AnyType extends Comparable<? super AnyType>> void mergeSort(AnyType[] a) {
        AnyType[] tmpArray = (AnyType[]) new Comparable[a.length];
        mergeSort(a, tmpArray, 0, a.length - 1);
    }

    public static <AnyType extends Comparable<? super AnyType>>
    void quicksort(AnyType[] a) {
        quicksort(a, 0, a.length - 1);
    }

    private static <AnyType extends Comparable<? super AnyType>>
    AnyType median3(AnyType[] a, int left, int right) {
        int center = (left + right) / 2;
        if (a[center].compareTo(a[left]) < 0) {
            swapReferences(a, left, center);
        }
        if (a[right].compareTo(a[left]) < 0) {
            swapReferences(a, left, right);
        }
        if (a[right].compareTo(a[center]) < 0) {
            swapReferences(a, center, right);
        }

        // Place pivot at position right - 1
        swapReferences(a, center, right - 1);
        return a[right - 1];
    }

    private static <AnyType extends Comparable<? super AnyType>>
    void insertionSort(AnyType[] a, int left, int right) {
        int j;
        for (int p = left; p <= right; p++) {
            AnyType tmp = a[p];
            for (j = p; j > 0 && tmp.compareTo(a[j - 1]) < 0; j--) {
                a[j] = a[j - 1];
            }
            a[j] = tmp;
        }
    }

    private static <AnyType extends Comparable<? super AnyType>>
    void quicksort(AnyType[] a, int left, int right) {
        if (left + 10 <= right) {
            AnyType pivot = median3(a, left, right);

            // Begin partitioning
            int i = left, j = right - 1;
            for (; ; ) {
                while (a[++i].compareTo(pivot) < 0) {
                }
                while (a[--j].compareTo(pivot) > 0) {
                }
                if (i < j) {
                    swapReferences(a, i, j);
                } else {
                    break;
                }
            }

            swapReferences(a, i, right - 1); // Restore pivot

            quicksort(a, left, i - 1); // Sort small elements
            quicksort(a, i + 1, right); // Sort large elements
        } else // Do an insertion sort on the subarray
        {
            insertionSort(a, left, right);
        }
    }

    public static void bucketSort(int[] num) {

        int max = num[0];
        for (int i = 0; i < num.length; i++) {
            if (num[i] > max) {
                max = num[i];
            }
        }

        int[] bucketArray = new int[max + 1];
        for (int i = 0; i < num.length; i++) {
            bucketArray[num[i]]++;
        }
        int index = 0;
        for (int i = 0; i < bucketArray.length; i++) {
            for (int j = 0; j < bucketArray[i]; j++) {
                num[index++] = i;
            }
        }
    }

    public static void radixSort(Integer[] a) {
        Integer[] b = a;
        int max = b[0];
        for (int i = 1; i < b.length; i++) {
            if (b[i] > max) {
                max = b[i];
            }
        }
        int maxLength = (max + "").length();

        int[][] bucket = new int[10][b.length];
//        ArrayList<Integer> [] bucket = new ArrayList<Integer>[10];

        int[] bucketElementCounts = new int[10];
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < b.length; j++) {
                int digitOfElement = b[j] / n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = b[j];
                bucketElementCounts[digitOfElement]++;
            }
            int index = 0;
            for (int j = 0; j < bucketElementCounts.length; j++) {
                if (bucketElementCounts[j] != 0) {
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        b[index++] = bucket[j][k];
                    }
                }
                bucketElementCounts[j] = 0;
            }
        }
    }
}